package reviewAlgorithms.search;

import java.util.*;

public class MaxAreaOfIsland {
    public static void main(String[] args) {
//        int[][] grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
//                         {0,0,0,0,0,0,0,1,1,1,0,0,0},
//                         {0,1,1,0,1,0,0,0,0,0,0,0,0},
//                         {0,1,0,0,1,1,0,0,1,0,1,0,0},
//                         {0,1,0,0,1,1,0,0,1,1,1,0,0},
//                         {0,0,0,0,0,0,0,0,0,0,1,0,0},
//                         {0,0,0,0,0,0,0,1,1,1,0,0,0},
//                         {0,0,0,0,0,0,0,1,1,0,0,0,0}};
        int[][] grid = {{0,1,1},
                        {1,1,0}};
        System.out.println(maxAreaOfIsland(grid));

    }
    public static int maxAreaOfIsland(int[][] grid) {
        if (grid.length < 1) {
            return 0;
        }
        int rowNum = grid.length;
        int columnNum = grid[0].length;
        int maxNum = rowNum * columnNum;
        int maxArea = 0;
        int[][] stage = new int[rowNum][columnNum];
        for (int i = 0; i < rowNum; i++) {
            Arrays.fill(stage[i],1);
        }
        int row;
        int column;
        for (int i = 0; i < maxNum; i++) {
            row = i / columnNum ;
            column = i % columnNum;
            if (stage[row][column] == 1 && grid[row][column] == 1) {
                maxArea = Math.max(maxArea,getAreaDiGui(grid,row,column,stage));
            }
        }
        return maxArea;
    }

    private static int getAreaDiGui(int[][] grid, int row, int column, int[][] stage) {
        if (row < 0 || column < 0 || row >= grid.length || column >= grid[0].length || stage[row][column] == 0 || grid[row][column] == 0){
            return 0;
        }
        stage[row][column] = 0;
        int num = 1;
        num+= getAreaDiGui(grid,row + 1,column,stage);
        num+= getAreaDiGui(grid,row - 1,column,stage);
        num+= getAreaDiGui(grid,row,column + 1,stage);
        num+= getAreaDiGui(grid,row,column - 1,stage);
        return num;
    }

    private static int getArea(int[][] grid, int row, int column, int[][] stage) {
        Stack<int[]> processStack = new Stack<>();
        int[] location = new int[2];
        location[0] = row;
        location[1] = column;
        processStack.add(location);
        stage[location[0]][location[1]] = 0;
        int area = 0;
        while (!processStack.empty()){
            location = processStack.pop();
            area ++;
            List<int[]> nextLocation = getNestLocation(location,grid,stage);
            processStack.addAll(nextLocation);
        }
        return area;
    }

    private static List<int[]> getNestLocation(int[] location, int[][] grid, int[][] stage) {
        List<int[]> nextLocation = new ArrayList<>();
        if (location[0] - 1 >= 0 && stage[location[0] - 1][location[1]] == 1 && grid[location[0] - 1][location[1]] == 1){
            int[] locationTemp = new int[2];
            locationTemp[0] = location[0] - 1;
            locationTemp[1] = location[1];
            nextLocation.add(locationTemp);
            stage[locationTemp[0]][locationTemp[1]] = 0;
        }
        if (location[0] + 1 < grid.length && stage[location[0] + 1][location[1]] == 1 && grid[location[0] + 1][location[1]] == 1){
            int[] locationTemp = new int[2];
            locationTemp[0] = location[0] + 1;
            locationTemp[1] = location[1];
            nextLocation.add(locationTemp);
            stage[locationTemp[0]][locationTemp[1]] = 0;
        }
        if (location[1] - 1 >= 0 && stage[location[0]][location[1] - 1] == 1 && grid[location[0]][location[1] - 1] == 1){
            int[] locationTemp = new int[2];
            locationTemp[0] = location[0];
            locationTemp[1] = location[1] - 1;
            nextLocation.add(locationTemp);
            stage[locationTemp[0]][locationTemp[1]] = 0;
        }
        if (location[1] + 1 <grid[0].length && stage[location[0]][location[1] + 1] == 1 && grid[location[0]][location[1] + 1] == 1){
            int[] locationTemp = new int[2];
            locationTemp[0] = location[0];
            locationTemp[1] = location[1] + 1;
            nextLocation.add(locationTemp);
            stage[locationTemp[0]][locationTemp[1]] = 0;
        }
        return nextLocation;
    }
}
